package Leetcode.数组字符串;

import java.util.Arrays;
import java.util.Comparator;

/**
 * @ClassName 用最少数量的箭引爆气球
 * @since: 2023/8/31 09:15
 * @auth: kirito
 * @description:
 * 同删除重叠区间后的区间数
 **/
public class 用最少数量的箭引爆气球 {
    public int findMinArrowShots(int[][] points) {
        if (points.length <= 1) {
            return points.length;
        }
        int res = 1;
        // 先按照区间起始位置排序   按照第二个值进行升序排列  避免按照第一个排序造成多个重叠问题
        Arrays.sort(points, (v1, v2) -> Integer.compare(v1[1], v2[1]));
//        如果按左端升序排序，可能出现这种：[0, 9], [0, 6], [7, 8]
//
//        当前第一个区间和第二个重合，我让当前第一个区间继续寻求重合，它和第三个也重合。
//        你想着一箭三雕，但第二个和第三个其实并不重合。
//        被「包含」在当前区间的重合区间，不一定和别的重合区间重合
//        当前区间可能和很多区间重合，但无法保证这些区间内部都互相重合。
//
//        如果按右端升序排序，就杜绝了「前面包后面」的情况。
//
//        画个图就好理解为什么了

//        // 使用第二个代码片段进行排序（按照第二个值升序）
//        Arrays.sort(points, new Comparator<int[]>() {
//            public int compare(int[] point1, int[] point2) {
//                if (point1[1] > point2[1]) {
//                    return 1;
//                } else if (point1[1] < point2[1]) {
//                    return -1;
//                } else {
//                    return 0;
//                }
//            }
//        });
        int[] temp = points[0]; // 初始化 temp 为第一个区间
        for (int i = 1; i < points.length; i++) {
            if (temp[1] < points[i][0]) { // 如果 temp 的结束位置小于当前区间的起始位置
                res++; // 需要增加一支箭
                temp = points[i]; // 更新 temp 为当前区间
            }
        }
        return res;
    }
}
